package com.moyoutian.leetcode.interview;


/**
 * 面试题 17.14. 最小K个数
 * <p>
 * 设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
 * <p>
 * 示例：
 * <p>
 * 输入： arr = [1,3,5,7,2,4,6,8], k = 4
 * 输出： [1,2,3,4]
 * <p>
 * 提示：
 * <p>
 * 0 <= len(arr) <= 100000
 * 0 <= k <= min(100000, len(arr))
 */
public class Demo7 {

    //9：34
    public static void main(String[] args) {
        int[] arr = {0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1};
        int k = 4;

        smallestK(arr, 5);
    }

    /**
     * 计算数组中第k小的数
     *
     * @param arr 数组
     * @param k   第k
     * @return 将数组中k之前的数放到k之前
     */
    public static int[] smallestK(int[] arr, int k) {

        //数组中是存在重复数据的，如果 数组是[0,0,0,0,1,1,1,1,1,1,1,1,2,2,2,2]当=3时还是1前面的。所以相等的值应该在第k的左边。
        //第k小也就是k左边要有k-1个数比k小的数，且k右边都是大于k的数，即可。
        //也就是用第k小的数将数组分成两半即可,贴近于二分法。所以用二分法处理。快查
        if (k == 0) {
            return new int[0];
        } else if (k == arr.length - 1) {
            return arr;
        }
        int[] re = new int[k];
        if (k < arr.length - 1) {

            int l = 0;
            int r = arr.length - 1;
            while (l < r) {
                //随机选取一个数字，用这个数字做基准。将数组分成两半
                int temp = arr[r];
                int tagL = l;
                int tagR = r;
                while (l < r) {
                    while (temp > arr[l] && l < r) {
                        l++;
                    }
                    while (temp <= arr[r] && l < r) {
                        r--;
                    }
                    //每一次检查完毕，需要做交换
                    sw(arr, l, r);

                }
                //最终交换基准数
                sw(arr, l, tagR);

                //每分割结束之后,先判断当前分割是否满足结果。否则重新选取左右坐标
                //满足条件直接退出循环，返回结果
                if (l == k) {
                    break;
                }
                //l坐标小于k，证明左边不够，需要向右移动，否则向左移动
                else if (l < k) {
                    //向右移动，l位移上一步的终点+1，r需要回归到分割之前。
                    l++;
                    r = tagR;
                } else {
                    r--;
                    l = tagL;
                }
            }

            for (int i = 0; i < k; i++) {
                re[i] = arr[i];
            }

        }

        return re;
    }

    public static void sw(int[] arr, int l, int r) {
        int tempS = arr[l];
        arr[l] = arr[r];
        arr[r] = tempS;
    }


}
